package algorithm.difficult;

import org.jcp.xml.dsig.internal.dom.DOMXMLObject;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。
 * <p>
 * 给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。
 * <p>
 * 当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
 * <p>
 * 另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。
 * <p>
 * 返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/grid-illumination
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GridIllumination1001 {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        //x,y,正反对角线，每条线包含灯的数量，key为唯一决定值
        HashMap<Integer, Integer> xMap = new HashMap<>();
        HashMap<Integer, Integer> yMap = new HashMap<>();
        HashMap<Integer, Integer> zMap = new HashMap<>();
        HashMap<Integer, Integer> fMap = new HashMap<>();
        //用一个set保存当前点的状态
        HashSet<Long> set = new HashSet<>();
        for (int[] arr : lamps) {
            if (!set.add(hash(arr[0], arr[1]))) {
                continue;
            }
            int x = arr[0];
            int y = arr[1];
            xMap.put(x, xMap.getOrDefault(x, 0) + 1);
            yMap.put(y, yMap.getOrDefault(y, 0) + 1);
            zMap.put(x - y, zMap.getOrDefault(x - y, 0) + 1);
            fMap.put(x + y, fMap.getOrDefault(x + y, 0) + 1);
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < res.length; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            //如果当前map不为空，说明有灯可以照亮
            if (xMap.getOrDefault(x, 0) > 0) {
                res[i] = 1;
            } else if (yMap.getOrDefault(y, 0) > 0) {
                res[i] = 1;
            } else if (zMap.getOrDefault(x - y, 0) > 0) {
                res[i] = 1;
            } else if (fMap.getOrDefault(x + y, 0) > 0) {
                res[i] = 1;
            }
            //灭灯，在附近3*3方格内
            for (int j = x - 1; j <= x + 1; j++) {
                for (int k = y - 1; k <= y + 1; k++) {
                    //取值范围
                    if (j < 0 || j >= n || y < 0 || y >= n) {
                        continue;
                    }
                    //关掉当前位置灯，不是关灯光
                    if (set.contains(hash(j, k))) {
                        xMap.put(j, xMap.getOrDefault(x, 0) - 1);
                        if (xMap.get(j) <= 0) {
                            xMap.remove(j);
                        }
                        yMap.put(k, yMap.getOrDefault(y, 0) - 1);
                        if (yMap.get(k) <= 0) {
                            yMap.remove(k);
                        }
                        zMap.put(j - k, zMap.getOrDefault(j - k, 0) - 1);
                        if (zMap.get(j - k) <= 0) {
                            zMap.remove(j - k);
                        }
                        fMap.put(j + k, fMap.getOrDefault(j + k, 0) - 1);
                        if (fMap.get(j + k) <= 0) {
                            fMap.remove(j + k);
                        }
                        set.remove(hash(j, k));
                    }
                }
            }
        }
        return res;
    }

    public long hash(int x, int y) {
        return (long) x + ((long) y << 32);
    }

//    public static void main(String[] args) {
//        long l = Integer.MAX_VALUE;
//        double d = 2*Math.pow(10,9);
//        System.out.println(l);
//        System.out.println(d);
//        System.out.println(l-d);
//    }
}
